{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The MAB problem\n",
    "\n",
    "The MAB problem is one of the classic problems in reinforcement learning. A MAB\n",
    "is a slot machine where we pull the arm (lever) and get a payout (reward) based on\n",
    "some probability distribution. A single slot machine is called a one-armed bandit and\n",
    "when there are multiple slot machines it is called a MAB or k-armed bandit, where k\n",
    "denotes the number of slot machines.\n",
    "\n",
    "The following figure shows a 3-armed bandit:\n",
    "\n",
    "\n",
    "![title](Images/7.png)\n",
    "\n",
    "Slot machines are one of the most popular games in the casino, where we pull the\n",
    "arm and get a reward. If we get 0 reward then we lose the game, and if we get +1\n",
    "reward then we win the game. There can be several slot machines, and each slot\n",
    "machine is referred to as an arm. For instance, slot machine 1 is referred to as arm\n",
    "1, slot machine 2 is referred to as arm 2, and so on. Thus, whenever we say arm n,\n",
    "it actually means that we are referring to slot machine n.\n",
    "\n",
    "Each arm has its own probability distribution indicating the probability of winning\n",
    "and losing the game. For example, let's suppose we have two arms. Let the\n",
    "probability of winning if we pull arm 1 (slot machine 1) be 0.7 and the probability\n",
    "of winning if we pull arm 2 (slot machine 2) be 0.5.\n",
    "\n",
    "\n",
    "Then, if we pull arm 1, 70% of the time we win the game and get the +1 reward, and\n",
    "if we pull arm 2, then 50% of the time we win the game and get the +1 reward.\n",
    "Thus, we can say that pulling arm 1 is desirable as it makes us win the game 70% of\n",
    "the time. However, this probability distribution of the arm (slot machine) will not\n",
    "be given to us. We need to find out which arm helps us to win the game most of the\n",
    "time and gives us a good reward.\n",
    "\n",
    "Okay, how can we find this?\n",
    "\n",
    "Say we pulled arm 1 once and received a +1 reward, and we pulled arm 2 once\n",
    "and received a 0 reward. Since arm 1 gives a +1 reward, we cannot come to the\n",
    "conclusion that arm 1 is the best arm immediately after pulling it only once. We need\n",
    "to pull both of the arms many times and compute the average reward we obtain from\n",
    "each of the arms, and then we can select the arm that gives the maximum average\n",
    "reward as the best arm.\n",
    "\n",
    "Let's denote the arm by a and define the average reward by pulling the arm a as:\n",
    "\n",
    "$$ Q(a) \\frac{\\text{Sum of rewards obtained from the arm}}{\\text{Number of times the arm was pulled}}$$\n",
    "\n",
    "Where $Q(a)$ denotes the average reward of arm $a$.\n",
    "The optimal arm $a^*$ is the one that gives us the maximum average reward, that is:\n",
    "\n",
    "$$ a^* = \\text{arg} \\max_a Q(a) $$\n",
    "\n",
    "Okay, we have learned that the arm that gives the maximum average reward is the\n",
    "optimal arm. But how can we find this?\n",
    "\n",
    "We play the game for several rounds and we can pull only one arm in each round.\n",
    "Say in the first round we pull arm 1 and observe the reward, and in the second round\n",
    "we pull arm 2 and observe the reward. Similarly, in every round, we keep pulling\n",
    "arm 1 or arm 2 and observe the reward. After completing several rounds of the\n",
    "game, we compute the average reward of each of the arms, and then we select the\n",
    "arm that has the maximum average reward as the best arm.\n",
    "\n",
    "But this is not a good approach to find the best arm. Say we have 20 arms; if we keep\n",
    "pulling a different arm in each round, then in most of the rounds we will lose the\n",
    "game and get a 0 reward. Along with finding the best arm, our goal should be to\n",
    "minimize the cost of identifying the best arm, and this is usually referred to as regret.\n",
    "\n",
    "\n",
    "Thus, we need to find the best arm while minimizing regret. That is, we need to find\n",
    "the best arm, but we don't want to end up selecting the arms that make us lose the\n",
    "game in most of the rounds.\n",
    "\n",
    "So, should we explore a different arm in each round, or should we select only the\n",
    "arm that got us a good reward in the previous rounds? This leads to a situation\n",
    "called the exploration-exploitation dilemma, which we learned about in Chapter\n",
    "4, Monte Carlo Methods. So, to resolve this, we use the epsilon-greedy method and\n",
    "select the arm that got us a good reward in the previous rounds with probability\n",
    "1-epsilon and select the random arm with probability epsilon. After completing\n",
    "several rounds, we select the best arm as the one that has the maximum average\n",
    "reward.\n",
    "\n",
    "Similar to the epsilon-greedy method, there are several different exploration\n",
    "strategies that help us to overcome the exploration-exploitation dilemma. In the\n",
    "upcoming section, we will learn more about several different exploration strategies\n",
    "in detail and how they help us to find the optimal arm, but first let's look at\n",
    "creating a bandit.\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
